package com.leetcode;

import java.util.Arrays;

/**
 * 416. 分割等和子集
 * 给你一个 只包含正整数 的 非空 数组 nums 。请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 */
public class LeetCode416 {

    public static void main(String[] arg0) {
        int[] nums = new int[]{1, 5, 11, 5};

        Arrays.sort(nums);
        long sum = Arrays.stream(nums).sum();
        boolean res = false;
        long halfSum = sum / 2;
        if (sum % 2 == 0 && nums[nums.length - 1] <= halfSum) {
            if (nums[nums.length - 1] == halfSum) {
                res = true;
            } else {
                boolean[] dp = new boolean[(int) (halfSum + 1)];
                dp[0] = true; // 和为0的子集总是存在（空集）

                for (int num : nums) {
                    // 从后向前更新dp数组
                    for (int j = (int) halfSum; j >= num; j--) {
                        dp[j] = dp[j] || dp[j - num];
                    }
                }

                res = dp[(int) halfSum];
            }
        }

        System.out.println("res: " + res);
    }

}
